package com.caoyanan.algorithm.question.zuoTraining.training004.class02;

/**
 * 骑士找公主
 *
 * 给定一个二维数组 map，含义是一张地图，例如，如下矩阵:
 * -2 -3   3
 * -5 -10  1
 *  0  30 -5
 * 游戏的规则如下:
 * 骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
 * 地图中每个位置的值代表骑士要遭遇的事情。
 * 如果是负数，说明此处有怪兽，要让骑士损失血量。
 * 如果是非负数，代表此处有血瓶，能让骑士回血。
 * 骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。
 * 为了保证骑士能见到公主，初始血量至少是多少?根据map，返回至少的初始血量。
 *
 * @author: caoyanan
 * @time: 2021/6/4 3:01 下午
 */
public class Question01_KnightLookingForPrincess {

    public static void main(String[] args) {

        int[][] arr = {{-2, -3, 3}, {-5, -10, 1}, {0, 30, -5}};
        System.out.println(process(arr));
    }

    /**
     * 此道题是一个动态规划，要求从[0][0]位置到右下角找公主，最少需要多少血量，
     * 那就准备一个数组dp[i][j],表示从[i][j]位置到右下角找到公主，需要多少血量(任何一个位置，血量都不能少于1）
     * dp[rowMax][columnMax] = arr[rowMax][columnMax] > 0 ? 0 : 1-arr[rowMax][columnMax]
     * 填最后一列 dp[rowMax][j],
     *      首先 arr[rowMax][j]要过去 arr[rowMax][j] > 0 ? 0 : (1-arr[rowMax][j]),
     *      然后后面到达终点，再加上后面需要的血量dp[rowMax][j+1]，然后此时可能比后面的血量还高，或者比后面的血量还低,最后取最高的血量
     *      Math.max(   arr[rowMax][j] > 0 ? 0 : (1-arr[rowMax][j]),      dp[rowMax][j+1])
     *
     * 对于一个普遍位置 dp[i][j]
     *  首先，arr[i][j]的位置要能过去  即   arr[i][j] > 0 ? 0 : 1-arr[i][j]
     *  然后，决定走右边还是走下边，  nextNeedBlood = Math.min( dp[i+1][j](下) + dp[i][j+1](右))
     *  然后，看一下 nextNeedBlood 和自己的 currentNeedBlood 谁大谁小  Math.max(nextNeedBlood, currentNeedBlood)
     *  这个是错的，比如 currentNeedBlood是0，当前血包是30，后续nextNeedBlood = 6。 Math.max(6, 0) = 6。得出当前需要6初始血量，其实当前需要0初始血量就可以了
     *  应该是， Math.max(nextNeedBlood-arr[i][j], currentNeedBlood) ，因为 nextNeedBlood 一部分被当前血包给 顶上了。
     *  但是 如果 arr[i][j] < 0，就不用减了， 即 Math.max( arr[i][j] > 0 ? nextNeedBlood - arr[i][j] : nextNeedBlood, currentNeedBlood)
     *  也就等于 Math.max(走下面节点需要多少血量(下面需要的血量被当前节点消耗一部分)，
     *                      经过当前节点需要需要消耗多少血量),
     *          Math.max(arr[i][j] > 0 ? nextNeedBlood - arr[i][j] : nextNeedBlood ,
     *                      arr[i][j] > 0 ? 0 : 1-arr[i][j] ;
     *  但这其实就等于 Math.max(nextNeedBlood - arr[i][j], 1)
     *
     * 整张表是先填最后一行，最有一列，然后剩下的填表过程是从右向左，从下到上
     * @param arr
     * @return
     */
    private static int process(int[][] arr) {

        int rowMax = arr.length-1;
        int columnMax = arr[0].length-1;
        int[][] dp = new int[rowMax+1][columnMax+1];

        // 最右下角
        dp[rowMax][columnMax] = arr[rowMax][columnMax] > 0 ? 0 : 1 - arr[rowMax][columnMax];

        //填最后一行
        for (int j = columnMax-1; j >= 0; j--) {
            // 自己需要的血量
            dp[rowMax][j] = Math.max(1, dp[rowMax][j + 1] - arr[rowMax][j]);
        }

        // 填最右边一列
        for (int i = rowMax - 1; i >= 0; i--) {
            dp[i][columnMax] = Math.max(1, dp[i + 1][columnMax] - arr[i][columnMax]);
        }

        // 填普遍位置
        for (int i = rowMax - 1; i >= 0; i--) {
            for (int j = columnMax - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i][j+1], dp[i+1][j]) - arr[i][j]);
            }
        }
        return dp[0][0];
    }
}
